from collections import Counter

MOD = 10 ** 9 + 7


class Solution:
    def numberOfCombinations(self, num: str) -> int:
        num = [int(ch) for ch in num]
        n = len(num)

        # 处理第1位为0的情况
        if num[0] == 0:
            return 0

        # 所有数字完全相同的模式
        all_same_mode = (set(num) == 1)

        # 定义状态表格：dp[i] = {前一个数位数:方案数,...}
        dp = [Counter() for _ in range(n + 1)]

        # 处理第一位的情况
        dp[n][n] += 1
        for i in range(1, n // 2 + 1):
            dp[i][i] += 1

        # 处理其他位的情况
        for i in range(1, n):
            print(i, ":", dp[i])

            # 剩余的数字数量
            surplus = n - i

            # 处理当前位为0的情况
            if num[i] == 0:
                continue

            # 遍历所有前一位的数位数和方案数
            for bit, v in dp[i].items():
                # 如果剩下的位数没有上一位的数位多，则放弃当前分支
                if bit > surplus:
                    continue

                # 如果剩下的位数和上一位的数位一样多，则比较当前分支是否能得到答案
                elif bit == surplus:
                    j1, j2 = i - bit, i
                    if all_same_mode or num[j1:j2] <= num[j2:n]:
                        dp[n][surplus] = (dp[n][surplus] + v) % MOD

                # 如果剩下的位数比上一位的数位多
                else:
                    # 增加直接到最后一位的方案
                    dp[n][surplus] = (dp[n][surplus] + v) % MOD

                    # 处理下一位和当前位长度相同的情况
                    j1, j2, j3 = i - bit, i, i + bit
                    if all_same_mode or num[j1:j2] <= num[j2:j3]:
                        dp[j3][bit] = (dp[j3][bit] + v) % MOD

                    # 累加下一位比当前位更长的情况
                    for j in range(bit + 1, surplus // 2 + 1):
                        dp[i + j][j] = (dp[i + j][j] + v) % MOD

        print(dp)

        return sum(dp[-1].values()) % MOD


if __name__ == "__main__":
    print(Solution().numberOfCombinations(num="327"))  # 2
    print(Solution().numberOfCombinations(num="094"))  # 0
    print(Solution().numberOfCombinations(num="0"))  # 0
    print(Solution().numberOfCombinations(num="9999999999999"))  # 101

    # 自制用例 5
    print(Solution().numberOfCombinations(num="4499"))

    # 测试用例256/257
    print(Solution().numberOfCombinations(num="1" * 3500))
